﻿#pragma once
#include "RBTree.h"

namespace bit {
	template <class K>
	class set {
	public:
		struct SetKeyOfT {
			const K& operator() (const K& key) { return key; }
		};

		//红黑树的迭代器提供的是最基础的遍历功能，它只是简单地封装了节点指针，
		//并提供 operator++、operator--、operator* 等基本操作。
		//set 和 map 需要更严格的迭代器控制
		//由于set和map的键（key）是排序的依据，必须保证键的不可变性，否则会破坏红黑树的有序性。因此：
		//set的iterator和const_iterator都必须是const 迭代器（即 RBTree::const_iterator）。
		//map 的 iterator 允许修改 value（pair.second），但禁止修改 key（pair.first）。
		//map 的 const_iterator 完全禁止修改（key 和 value 都不能改）。

		//typedef RBTree<K, K, SetKeyOfT>::iterator iterator;
		//在模板编程中，当一个类型（如 iterator）依赖于模板参数（如 K）时，它被称为 “嵌套依赖类型”。
		//这里，RBTree<K, K, SetKeyOfT>::iterator 的类型取决于模板参数 K，因此它是一个 嵌套依赖类型。
		//C++ 编译器在解析模板时有一个特殊规则：
		//默认情况下，编译器假定嵌套依赖名称（如 X::Y）是一个静态成员变量，而不是类型。
		//如果 iterator 确实是类型，但未用 typename 声明，编译器会尝试将其解释为变量，导致错误。
		//解决方案：必须用 typename 显式告诉编译器：“RBTree<K, ...>::iterator 是一个类型，而不是变量”。
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
		//set只有key且不能修改，所以iterator和const_iterator都使用const_iterator
		iterator begin() const { return _t.begin(); }
		iterator end() const { return _t.end(); }

		pair<iterator, bool> Insert(const K& key) { return _t.Insert(key); }
		//仅仅将两个迭代器都改为const_iterator还是会报错
		//set的Insert返回类型：其中 iterator 是 RBTree<K, K, SetKeyOfT>::const_iterator，
		//即 __TreeIterator<T, const T&, const T*>。
		//RBTree的Insert返回类型：其中iterator 是 __TreeIterator<T, T&, T*>（非 const 版本）。
	private:
		RBTree<K, K, SetKeyOfT> _t;
		//set不能使用RBTree<const K, const K, SetKeyOfT> _t;
		//虽然set的key不能修改，但是可能需要调整节点（如红黑树的旋转、变色）
		//这些操作可能需要临时修改节点的 data（例如之前二叉搜索树的删除，需要交换节点）
		//const K 会阻止这些操作，导致 RBTree 无法完成插入/删除的调整逻辑。
	};
}
//红黑树的模版参数template <class K, class T, class KeyOfT>
//K的作用：K是键（Key）的类型，用于：比较节点：红黑树需要比较节点的键来决定插入、查找的位置。
//KeyOfT 仿函数从 T 中提取键（K）。
//set的T就是key，但map的T是pair<const K, V>。
//如果红黑树没有第一个参数K，那么set和map的比较、查找的逻辑就不一样。
//set可以直接使用T，但map需要先从T中获取key。这样红黑树的类模板就没办法做到统一。